package cn.ly.series;

import cn.ly.util.ArithmeticTool;

public class SeriesSumTest {
	
	public static void main(String[] args) {
		int[] arr = new int[20];
		for(int i=0; i < arr.length; i++){
			arr[i] = ArithmeticTool.getIntRandomto100();
		}
		for(int i=0; i < arr.length; i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		
		getSeriesMaxSumByFN(arr);
		getSeriesMaxSumByFN2(arr);
		
	}
	
	//时间复杂度f(n)，当遍历序列时，遇见小于0的数时，去判断sum，如果sum也小于0，则丢弃这个数
	public static int getSeriesMaxSumByFN(int[] arr){
		int tempMax = 0;
		int tempSum = 0;
		for(int i = 0; i < arr.length; i++){
			tempSum = arr[i] + tempSum;
			if(arr[i] < 0){
				if(tempSum < 0){
					tempSum = 0;
				}
				continue;
			}else{
				if(tempSum > tempMax){
					tempMax = tempSum;
				}
			}
		}
		System.out.println("fn max : " + tempMax);
		return tempMax;
	}
	
	//时间复杂度f(n的2次方)
	public static int getSeriesMaxSumByFN2(int[] arr){
		int temp = 0;
		int maxSum = 0;
		for(int i = 0; i < arr.length; i++){
			for(int j = i; j < arr.length; j++){
				temp = temp + arr[j];
				if(temp > maxSum){
					maxSum = temp;
				}
			}
			temp = 0;
		}
		System.out.println("fn2 max : " + maxSum);
		return maxSum;
	}

}
